The following abbreviations are herewith defined, at least some of which are referred to within the following description of the state-of-the-art and the present invention. The reference to the “present invention” or “invention” used herein relates to exemplary embodiments and not necessarily to every embodiment that is encompassed by the appended claims.
AWGNAdditive White Gaussian NoiseBCHBroadcast ChannelBPSKBinary Phase-Shift KeyingCDMCode Division MultiplexingCDMACode Division Multiple AccessDFEDecision Feedback EqualizationFECForward Error CorrectionG-RAKEGeneralized-RAKEHSDPAHigh-Speed-Downlink-Packet AccessHSPAHigh Speed Packet AccessISIInter-Symbol InterferenceLDPCLow Density Parity Check CodeLELinear EqualizationLTELong Term EvolutionMIMOMultiple Input Multiple OutputMISOMultiple Input Single OutputMLSEMaximum Likelihood Sequence EstimationQAMQuadrature Amplitude ModulationRFRadio FrequencySIMOSingle Input Multiple OutputSISOSingle Input Single OutputTDMTime Division MultiplexingWCDMAWideband Code Division Multiple Access
Cellular communication systems are evolving these days to have even higher data rates. For instance, HSPA communication systems provide higher data rates in both uplink and downlink by using higher-order signal constellations to send more bits in the same amount of time. The same is true for the LTE uplink. However, when the channel between a transmitter and receiver is dispersive, then intersymbol interference (ISI) results, which limits the availability of high data rates.
Receivers have used linear equalization to suppress ISI. For instance, WCDMA (HSPA, HSDPA) receivers have suppressed ISI by using linear equalization schemes such as G-Rake or chip equalization. In addition, receivers have used linear equalization for the LTE uplink, though it is performed in the frequency domain. Basically, the linear equalizer at high signal power levels tries to undo the channel to eliminate the ISI. The problem is that there is room for improvement.
There are two main non-linear equalization approaches used today which can improve upon linear equalization: (1) decision feedback equalization (DFE); and (2) maximum likelihood sequence estimation (MLSE). DFE is only slightly more complex than linear equalization, but the performance gains are modest. The receiver could use a block DFE which can provide larger gains, but this does not completely close the gap with linear equalization due to the linear suppression of future ISI and error propagation from past ISI. The MLSE can close the gap in performance, but it is highly complex. There are various ways to approximate MLSE performance with simplifications. For instance, the MLSE can be simplified with path pruning approaches such as the M-algorithm and T-algorithm which are still fairly complex. Plus, these processes have a problem with the large constellations and in particular the large fanout size which is equal to the constellation size q. In addition, these processes require a certain level of complexity to let the detected sequence emerge from the pruning process. This is all described in greater detail below with respect to an exemplary non-spread MIMO communication system discussed next with respect to FIGS. 1-4 (PRIOR ART).
Exemplary Communication System
Referring to FIG. 1 (PRIOR ART), there is a basic diagram of a traditional non-spread MIMO communication system 100 with a transmitter 102 (including an encoder 104, an interleaver 106, a modulator 108 and multiple transmit antennas 110) coupled by a channel 112 to a receiver 114 (including multiple receive antennas 116, a demodulator 118, a deinterleaver 120 and a decoder 122). In operation, the encoder 104 receives a block of information bits 124 and protects those bits by mapping them into a larger block of modem bits 126. The encoder 104 can perform this by using an error control code such as a binary code, for example a BCH code, a LDPC code, a convolutional code, or a turbo code. The interleaver 106 receives the modem bits 126, changes the order/indices of the modem bits 126, and outputs re-ordered bits 128.
The modulator 108 receives the re-ordered bits 128 and uses a modulation constellation to output symbols 130. In particular, the modulator 108 uses the modulation constellation of size q to map log2 q consecutive bits into one of q modulation symbols when generating the output symbols 130. For instance, the modulator 108 can use a modulation constellation such as BPSK, with q=2, and 16-QAM, with q=16. The modulator 108 may also perform a filtering operation to produce partial response signaling. In addition, the modulator 108 may also perform a coded modulation operation, where the mapping of the current q bits depends on previous bits. For simplicity, the description provided herein will assume an un-coded modulation scheme. The modulation symbols are used to modulate an RF carrier.
The modulated symbols 130 are then transmitted by the transmit antennas 110 over the channel 112 to the receive antennas 116. The channel 112 represents the effects of fading in a wireless medium, the time dispersion, as well as the additive noise and interference on the transmitted symbols 130. Thus, the demodulator 118 receives a signal 132 which has been subjected to ISI. The ISI may also be due to the combined effects of partial response signaling and filtering at the transmitter 102, the multi-path dispersion over the wireless channel 112, and the filtering at the receiver 114. This channel model would also apply to other communication systems such as, for example, a CDMA system.
The receiver 114 performs the demodulation operation and the decoding operation separately. First, the demodulator 118 accepts the received signal 132, mitigates the ISI, and outputs estimates of the modem bits 134 in the form of soft bit values 134. The soft bit values 134 indicate the reliability of individual modem bits 126. The deinterleaver 120 receives the soft bit values 134 and changes their order/indices to be the reverse of that used by the interleaver 106. After de-interleaving, the re-ordered soft bit values 136 are fed to the decoder 122. The decoder 122 operates on the re-ordered soft bit values 136 to produce an estimate 138 of the information bits 124.
MIMO Demodulation Problem
The general MIMO demodulation problem is discussed next, with L1 transmit antennas 110 and L2 receive antennas 116. The transmitted and received signals 130 and 132 are represented by the vectors s=(s1,Λ,sL1)T and r=(r1,Λ,rL2)T, respectively.
Each component of s is a symbol from a finite modulation constellation. The set Q contains all possible transmitted vectors. The size q of Q is the product of the constellation sizes of the L1 components. That is, if L1=2 and both signals use 16 QAM, then q=256. In this discussion, assume q to be a power of 2.
At the transmitter 102, there is a one-to-one mapping from blocks of log2 q modem bits 126 to modulation symbols 130.
i. Dispersive Channel Model
For a symbol-spaced channel 112 with memory M, there are M+1 channel matrices HM,Λ,H0, each of dimensions L2×L1. The element Hm,i,j of Hm describes the channel 112 from transmit antenna j to receive antenna i at a delay of m symbols. The current transmitted signal s is denoted sk. The system model is given by:rk=HMsk−M+Λ+H1sk−1+H0sk+vk  (1)where vk=(vk,1,Λ,vk,L2)T represents the noise. For simplicity, an additive white Gaussian noise (AWGN) model in time and in space is considered.Equalizer Operation
The operation of the equalizer 118 (single stage equalizer 118) at the receiver 114 is discussed next. Assume that the transmitted signal 130 has a symbol vector sequence of length K. The receiver 114 processes the corresponding received values (r1,Λ,rk) to try to identify the best sequence in a maximum likelihood sense. The appropriate metric is the squared error (or Euclidean distance).
Given a full sequence hypothesis, the corresponding sequence metric can be computed. The sequence metric can be written as a sum of K partial metrics, called branch metrics. The name will become clear in light of the tree structure described later. In this discussion, the notation sa:b=(sa,Λ,sb) is adopted and a full sequence is denoted as s1K.
i. Branch Metric, Bias and Innovation
It is helpful to describe the branch metric in terms of bias and innovation. To account for the ISI properly in the model associated with equation no. 1 for k=1 to M, assume that the symbols s−M+10 are known. For now, think of these symbols as the known reference symbols. At index k, the bias vector associated with past symbols is given by:bk−1=HMsk−M+Λ+H1sk−1  (2)which is a function of the most recent M symbols sk−M:k−1 only. By removing the bias vector from the received vector, the innovation vector is obtained and can be represented by:ck=rk−bk−1.  (3)This innovation represents the residual received value after removing the bias. Finally ck is compared to the corresponding symbol weighted by the channel matrix, to obtain the branch metric represented by:∥ck−H0sk∥2.  (4)
ii. Sequence Metric
The sequence metric is given by:
                              ∑                      k            =            1                    K                ⁢                                                                                            c                  k                                -                                                      H                    0                                    ⁢                                      s                    k                                                                                      2                    .                                    (        5        )            The sequence metric of equation no. 5 is the appropriate measure which is used to compare different total sequence hypotheses. The best total sequence is the one that minimizes the sequence metric.
iii. MLSE
The MLSE finds the best total sequence. The Viterbi process is one very efficient way to search for the best total sequence. It does so by using intermediate steps, where same length subsequences are compared. A brief discussion about the operation of the MLSE is provided herein to provide a contrast to that of a stack algorithm (discussed below), where unequal length sequences are compared.
The MLSE operates on a trellis with qM states, and qM+1 branches per stage. The trellis has K+1 stages, indexed 0 to K, to handle the K received values. The MLSE starts at stage 0 and progresses towards stage K. At index k−1, each state represents a different combination of M symbols (sk−M,Λ,sk−1), and is labeled with an innovation according to equation nos. 2 and 3.
A branch representing a symbol sk starts from (sk−M,Λ,sk−1) and ends in state (sk−M+1,Λ,sk) at index k. The branch is labeled with a branch metric according to equation no. 4. This enables the computation of the sequence metric for sequence (s1,Λ,sk) of length k, as an update of the sequence metric for (s1,Λ, sk−1).
At each state of stage k, the sequence metrics for all the sequences of length k ending in that state are compared. All of the sequences but the one with the lowest sequence metric are discarded, and the survivor is kept. Eventually, the last stage K is reached. Each state has a length K surviving sequence. The survivor with the lowest sequence metric is the best overall sequence.
The MLSE has some drawbacks since it compares only the same length sequences. Plus, the number of states qM and the number of branches qM+1, which reflect the complexity of the MLSE process, grow very quickly with the modulation size Q or the memory M. Thus, as the number of states qM and the number of branches qM+1 get large, MLSE becomes hopelessly complex.
iv. Intuitive Justification of the Fano Metric
Anticipating the workings of the stack algorithm, suppose one wants to compare two unequal length subsequences s1:J and s′1:J with J<J′<K. Simply restricting the summation in equation no. 5 to J and J′ does not work well. For instance, taking the metric difference, one would obtain:
                                          ∑                          k              =              1                        J                    ⁢                      (                                                                                                                        c                      k                                        -                                                                  H                        0                                            ⁢                                              s                        k                        ′                                                                                                              2                            -                                                                                                            c                      k                                        -                                                                  H                        0                                            ⁢                                              s                        k                                                                                                              2                                      )                          +                              ∑                          k              =                              J                +                1                                                    J              ′                                ⁢                                                                                                          c                    k                                    -                                                            H                      0                                        ⁢                                          s                      k                      ′                                                                                                  2                        .                                              (        6        )            The second summation in equation no. 6 is unbalanced and always nonnegative, so the shorter sequence will tend to win out too easily.
To balance out the comparison, the missing symbols need to be accounted for in each sequence. This can be done by adding a bias βk that does not depend on the missing symbols, and represents an estimate of the branch metric. The resulting total sequence metric is given by:
                                          ∑                          k              =              1                        J                    ⁢                                                                                    c                  k                                -                                                      H                    0                                    ⁢                                      s                    k                                                                                      2                          +                              ∑                          k              =                              J                +                1                                      K                    ⁢                                    β              k                        .                                              (        7        )            
Furthermore, it is convenient to subtract the term
      ∑          k      =      1        K    ⁢      β    k  from equation no. 7. This has no effect on sequence metric comparisons. The resulting metric, denoted EJ, can be written as follows:
                              E          J                =                              ∑                          k              =              1                        J                    ⁢                                    (                                                                                                                                      c                        k                                            -                                                                        H                          0                                                ⁢                                                  s                          k                                                                                                                          2                                -                                  β                  k                                            )                        .                                              (        8        )            
The corresponding branch metric, denoted ek, is given by:ek=∥ck−H0sk∥2−βk  (9)
This is known as the Fano metric. For clarity, the metric difference is revisited and by using equation no. 8 the following is obtained:
                                          ∑                          k              =              1                        J                    ⁢                      (                                                                                                                        c                      k                                        -                                                                  H                        0                                            ⁢                                              s                        k                        ′                                                                                                              2                            -                                                                                                            c                      k                                        -                                                                  H                        0                                            ⁢                                              s                        k                                                                                                              2                                      )                          +                              ∑                          k              =                              J                +                1                                      K                    ⁢                                    (                                                                                                                                      c                        k                                            -                                                                        H                          0                                                ⁢                                                  s                          k                                                                                                                          2                                -                                  β                  k                                            )                        .                                              (        10        )            
The second sum in equation no. 10 is now balanced by the presence of βk, unlike that in equation no. 6. This confirms the intuitive explanation that the Fano branch metric provides a balance to the comparison of unequal length sequences.
v. Bias Example
Referring back to equation no. 7, it can be recalled that the bias βk is an estimate of the branch metric at indices where that metric has not been computed. Ideally, one would like to have an accurate and simple estimate because accuracy leads to better performance, while simplicity is in keeping with the low complexity equalizer.
The simplest bias is the vector noise power. This corresponds to the assumption that the hypothesized symbols sk−M:k which affect the branch metric at index k are correct. Then it can be seen from equation nos. 1-3 that equation no. 4 reduces to the following:∥ck−H0sk∥2=∥vk∥2.  (11)
The expected value of the right hand side is the vector noise power, denoted Pk. It can be estimated by averaging the error over recent symbols. Furthermore, for reasonably small values of the block length K, one can assume that the noise power is constant, so that the bias is a single value for all k. In general, the bias term can be proportional to the noise power. This approach and other approaches are described in T. Gucluoglu et al. “Soft Input Soft Output Stack Equalization for MIMO Frequency Selective Fading Channels,” in Proc. IEEE Intl. Conf. Commun., Seoul, Korea, May 16-20, 2005, pp. 510-514 (the contents of which are incorporated by reference herein).
Stack Algorithm
The stack algorithm is an aggressive depth first tree search process with a simple structure. It is well suited for scenarios where the state space is very large, making breadth first techniques like the Viterbi process impractical.
A key feature of the stack algorithm is the comparison of symbol sequences of different lengths, for the purpose of ranking them as more or less likely eventual solutions. This is made possible by using the aforementioned Fano metric.
The stack algorithm described below is used as a representative example, there are other sequential search processes that can be used such as the single-stack algorithm and bucket process. These other sequential search processes are described in J. B. Anderson et al. “Sequential Coding Algorithms: A Survey and Cost Analysis,” IEEE Transactions on Communications, vol. COM-32, February 1984 (the contents of which are incorporated by reference herein).
i. Search Tree
The stack algorithm operates on a tree of depth K. The root node of the tree, denoted Θ, is at index 0. It is associated with the null sequence φ of length 0. A node N at index k−1 is associated with its subsequence s1:k−1 starting from the root node. The fanout of node N is the set of branches B that start in N. Each branch is associated with a value for symbol sk. For now, assume there are no restrictions on the fanout, and it has q branches, one for each symbol vector in Q. The extension of node N by a branch B results in a new node N′ at index k, associated with the sequence s1:k. The new nodes N′ are referred to as the children, and N as the parent.
For reference purposes, one can think of the full tree of depth K, where each node is extended, and every possible sequence of length K is represented. FIG. 2 (Prior Art) illustrates an exemplary full tree 200 having a binary alphabet, q=2, and a depth K=3, and a root node Θ at index k=0. The exemplary full tree 200 also has branches B at index k which are labeled with the symbols sk.
The stack algorithm does not need to search the full tree 200, but instead it could focus on the most likely sequences. In this sense, the stack algorithm defines a sparse sub-tree of the full tree 200. FIG. 3 (Prior Art) illustrates an exemplary sparse tree 300 that can be created by a stack search with a binary alphabet, q=2, and a depth K=3. In this diagram, the nodes are labeled N(i) according to their rank in the stack.
ii. Branch and Node Metrics
In this discussion, consider a node N at index k−1, with the associated subsequence s1:k−1. The bias vector for N is explicitly denoted bk−1(N), and given by equation no. 2. The bias vector is a function of the most recent M symbols sk−M:k−1 only and summarizes the effect of node N on the branch metrics at index k.
The innovation vector, explicitly denoted ck(N), is obtained by removing the bias vector from the received vector as given by equation no. 3. The innovation vector represents the residual received value after removing the bias of node N.
For each branch B in the fanout of N, ck is compared to the corresponding symbol weighted by the channel matrix, to get the branch metric, explicitly denoted ek(B), and given by the Fano metric of equation no. 9. The branch metric ek(B) is a function of the most recent M+1 symbols sk−M:k only.
The squared error first term in equation no. 9 corresponds to Forney's approach to equalization which is discussed in G. D. Forney “Maximum-likelihood sequence estimation of digital sequences in the presence of intersymbol interference,” IEEE Trans. Info. Theory, vol. IT-18, May 1972 (the contents of which are incorporated by reference herein).
For a node N′ resulting from the extension of node N by a branch B, the node metric of N′ is given by:Ek(N′)=Ek−1(N)+ek(B)  (12)where Ek−1 (N) is the node metric of N. By default, the metric for node Θ is set to 0. Then using equation no. 12 one can build-up the node metric from node Θ to node N′.
An example of a node N extended via its fanout is shown in FIG. 4 (Prior Art). The exemplary node N is at index k−1=3 and is extended by the four branches in its fanout to produce four new children nodes N′ at k=4. The bias b3(N) is used in computing the branch metric e4(B). The sequence metric E4(N′) is computed from E3(N) and e4(B).
iii. Steps of Stack Algorithm
The stack algorithm includes an ordered list of nodes, with the best candidate on top (hence the term “stack”). The best node is removed from the stack and then extended via the branches in its fanout. The resulting new children nodes are slotted in the stack according to their sequence metric.
The stack algorithm is initialized with Θ. The stack algorithm stops when the node at the top of the stack has index k=K. The sequence of length K corresponding to that node is the output. Exemplary pseudo-code of the stack algorithm is as follows:
stack initialized with root nodeflag = 0while flag == 0  remove best node N from stack  extend node N with branches from its fanout  place new children nodes N’ in stack  if best node N has index = K    flag = 1  endendN corresponds to output symbol sequence
Referring again to the example in FIG. 3 (PRIOR ART), the nodes in the stack are labeled N(i) according to their rank. Since N(0) with index k=K is at the top of the stack, it is the winner. Its corresponding sequence (0,0,1) is the output of the stack algorithm.
Variants of the Stack Algorithm
i. Stack Size Growth
Each iteration of the stack algorithm removes one node and adds q nodes. Thus, the stack size keeps growing. For large q or long blocks K, this may be impractical. As a result, it may be necessary to limit the stack size.
One approach is to set a size limit. Once the stack exceeds that limit, it is trimmed back by removing the candidates at the bottom. As long as the limit is large enough, the impact on performance is minimal, since the trimmed candidates are the least likely to succeed.
Another approach is to set a sequence metric threshold. If a candidate's sequence metric exceeds that threshold, it is trimmed from the stack. Again, as long as the threshold is large enough, the impact on performance is minimal, since the trimmed candidates are the least likely to succeed.
ii. Merging Sequences
As discussed above, the stack algorithm operates on a tree. In this exemplary ISI scenario however, the state space is finite, and can be described by a trellis, where paths merge together. While it may not be needed to resort to a trellis here, it may be beneficial to exploit the merging idea.
The finite space is reflected in the fact that the bias is a function of the most recent M symbols only. Thus, if two nodes N and N′ at the same index k−1 agree in their most recent M symbols sk−M:k−1, then their bias vectors are equal:bk−1(N)=bk−1(N′).  (13)
Since nodes N and N′ have the same bias vectors, their branch metrics will be the same at index k. Furthermore, everything from this point forward will be the same. This means that the two nodes can be merged. To do so, their sequence metrics Ek−1(N) and Ek−1(N′) are compared and the node with the larger sequence metric is removed from the stack.
With an unbounded stack, merging nodes has no effect on performance, since the node with the larger sequence metric would never win. However, merging does affect complexity. Plus, one has to weigh the benefit of merging in reducing future operations, against the cost of keeping track of merging candidates, comparing them, and removing the worst ones.
With a bounded stack size, merging sequences may affect which nodes are trimmed. This is not likely to significantly impact performance.
With a stack limited by a metric threshold, the merging has no impact on performance.
iii. Getting Started (Initialization)
There are different ways to start the stack algorithm, depending on the transmission system. If pilot symbols are transmitted at the beginning, then the stack algorithm starts from a single, known state. In the absence of pilot symbols, there are several options. One is to start from multiple states corresponding to different combinations of the initial symbols. It may be necessary to initially perform a tree search/expansion before applying the stack pruning process. Merging sequences and stack pruning can be used to limit the increased number of sequences in the stack due to multiple initial states. Another option is to use information from the first stage to prune the multiple initial states to the most likely ones, including the extreme case of having a single starting state corresponding to detected symbol values from the first stage.
In view of the foregoing discussion about the various linear equalization approaches and the various non-linear equalization approaches, it can be seen that there is a need to address their various shortcomings to enable a receiver to effectively reduce the ISI in received symbols and output more reliable bits. This need and other needs are satisfied by the present invention.